package 剑指Offer._4150;

import java.util.HashMap;
import java.util.Map;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/15 15:25
 * 最长不含重复字符的子字符串
 * 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
 * 算法：滑动窗口
 * 遍历字符串，把字符加上去，如果碰到有重复的，
 * 那么就要把重复的以及之前的字符都删去
 */
public class _48 {
    public static void main(String[] args) {
//        String s = "ss1";
//        final int idx = s.indexOf("s");
//        System.out.println(idx);
//        System.out.println(s.substring(idx + 1));
        // "abba"
        System.out.println(new _48().lengthOfLongestSubstring_perfect("abba"));
    }

    public int lengthOfLongestSubstring(String s) {
        StringBuilder cur = new StringBuilder();
        int ans = 0;
        for (char c : s.toCharArray()) {
            final int idx = cur.indexOf(c + "");
            if (idx >= 0) cur = new StringBuilder(cur.substring(idx + 1));
            cur.append(c);
            ans = Math.max(ans, cur.length());
        }
        return ans;
    }

    /**
     * 上一个是使用字符串来表示滑动窗口，消耗空间大
     * 使用哈希表来存储滑动窗口中字符的位置，当遇到重复的字符时，左指针直接跳到这里
     * 但是 map 中还存储了重复字符之前的字符, 在更新左指针的时候，将 map 中存的位置跟
     * 当前左指针的值比较一下，如果比左指针的值还小，左指针就不变
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring_perfect(String s) {
        int l = 0, r = 0;
        int ans = 0;
        Map<Character, Integer> map = new HashMap<>(16);
        for (; r < s.length(); r++) {
            char c = s.charAt(r);
            if (map.containsKey(c)) l = Math.max(l, map.get(c) + 1);
            map.put(c, r);
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }

}
